package Algorithm.LRU;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU（Least Recently Used）即“最近最少使用”,这里使用双链表+hashMap实现了LRU算法
 * 注意：LRUCache中没有重复的节点
 *
 * @author chenjunjie
 * @since 2018-04-25
 */
public class LRUCache {
    Node head, tail;
    int size;
    int capacity;
    Map<Integer,Node> map;

    /**
     * 定义内部类，Node节点
     */
    static class Node {
        int key;
        int val;
        Node pre;
        Node post;

        /**
         * 构造函数
         * @param key Map的key
         * @param val May的value
         */
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }


    /**
     * 构造函数，初始化
     * @param capacity
     */
    public LRUCache(int capacity) {
        this.head = null;
        this.tail = null;
        this.size = 0;
        this.capacity = capacity;
        // 使用了HashMap
        // 注意这里Map中的value为Node类型，这样可以方便索引到某个具体node
        this.map = new HashMap<Integer, Node>();
    }


    /**
     * 获取最近使用node
     * 先remove掉节点以前所处位置，然后添加到链表的尾部，从而达到最近使用的效果
     * @param key
     * @return 返回value
     */
    public int get(int key) {
        if(!map.containsKey(key)) {
            return -1;
        }
        Node temp = map.get(key);
        remove(temp);
        add(temp);
        return temp.val;
    }

    /**
     * 添加新节点，并保证放入最后节点
     * @param key map的key值
     * @param value map中的value
     */
    public void put(int key, int value) {
        Node temp;
        // 如果之前有key，但不是放在链表尾部，则先删除然后添加到尾部
        if(map.containsKey(key)){
            temp = map.get(key);
            remove(temp);
            map.remove(key);
            size--;
        }

        // 如果超过了容量，这删除头部节点，即删除“最老”节点
        if(size == capacity){
            Node h = head;
            remove(h);
            map.remove(h.key);
            size--;
        }

        temp = new Node(key,value);
        // 链表中添加Node
        add(temp);
        // HashMap添加Entry
        map.put(key,temp);
        size++;
    }



    /**
     * 普通的linked链表删除操作
     * @param n 要删除的节点
     */
    private void remove(Node n) {
        // 如果只有一个节点
        if(n==head && n==tail){
            head = null;
            tail = null;
        }
        // 如果是头节点
        else if(n == head) {
            head = head.post;
            head.pre = null;
        }
        // 如果是尾节点
        else if(n == tail) {
            tail = tail.pre;
            tail.post = null;
        }
        //
        else{
            n.pre.post = n.post;
            n.post.pre = n.pre;
        }
        n.pre = null;
        n.post = null;
    }


    /**
     * 在链表尾部加入节点
     * @param n 添加节点
     */
    private void add(Node n) {
        if(head == null && tail == null) {
            head = n;
            tail = n;
        }else {
            tail.post = n;
            n.pre = tail;
            tail = n;
        }
    }


    /**
     * getMap，方便测试遍历查询结果
     * @return
     */
    public Map<Integer, Node> getMap() {
        return map;
    }

    /**
     * getHead，方便测试遍历查询结果,实际上不要暴露出来
     * @return
     */
    public Node getHead(){
        return head;
    }


}
